package com.mdnote.structure.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/28
 * @description 二分查找
 */
public class BinarySearch {

    /**
     * 二分查找
     * @param source 数组，必须是从大到小排好序的了
     * @param left 左边界
     * @param right 右边界
     * @param element 元素
     * @return 缩影
     */
    public static int searchOOne(int[] source, int left, int right, int element) {
        if (left > right) {
            // 已经找不到了
            return -1;
        }

        int mid = (left + right) / 2;
        if (element < source[mid]) {
            // 往左边找
            return searchOOne(source, left, mid - 1, element);
        } else if (element > source[mid]) {
            // 在右边
            return searchOOne(source, mid + 1, right, element);
        } else {
            // 找到了
            return mid;
        }
    }

    public static List<Integer> searchList(int[] source, int left, int right, int element) {

        if (left > right) {
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        if (element < source[mid]) {
            // 往左边找
            return searchList(source, left, mid - 1, element);
        } else if (element > source[mid]) {
            // 往右边找
            return searchList(source, mid + 1, right, element);
        } else {
            // 找到了
            List<Integer> res = new ArrayList<>();
            res.add(mid);
            int temp = mid - 1;
            // 往前找
            while (temp >= 0 && source[temp] == source[mid]) {
                res.add(temp);
                temp--;
            }
            // 往后找
            temp = mid + 1;
            while (temp >= 0 && source[temp] == source[mid]) {
                res.add(temp);
                temp++;
            }
            return res;
        }
    }

    public static void main(String[] args) {
        int[] data = {11, 11, 12, 12, 55};
        List<Integer> list = searchList(data, 0, data.length - 1, 12);
        System.out.println(list);
    }

}
